\chapter{Equivalence of Guesses}

\section{Overview}

Just as a human would be easy to identify equivalent guesses, we use that in computer as well.

[Isomorphism of guesses]

 * Precise definition of state equivalence should be on the
 * resulting partition. However, if computing that equivalence
 * is too expensive, we could instead compute the equivalence
 * of guesses.


\section{Prerequisites}

A \emph{constraint} is an associated pair of guess and response. A set of constraints is denoted $\vC$. When applied to a set of potential secrets, a constraint set selects a subset of the secrets that are consistent with those constraints. We call this subset  \emph{generated} by the constraint set. In particular, an empty constraint set generates all codewords.

A constraint set is called \emph{contradictory} if its generated secret set is empty, i.e.\ if no secret could satisfy all the constraints.

A constraint in a constraint set is called \emph{redundant} if the secrets generated from this constraint set is the same with or without that constraint. For example, the same constraint appearing twice is clearly redundant. Also, consider the example:
\[
\begin{array}{c}
\cw{1234} : \fb{0}{0} \\
\cw{3456} : \fb{0}{0} \\
\cw{1256} : \fb{0}{0} 
\end{array}
\]
Any one of the constraints is redundant.

A constraint set without redundant constraints is called \emph{irreducible}. In the following we are only interested in irreducible constraint sets.

Two constraint sets are \emph{equal} in the traditional set-equal sense, i.e.\ if they contain the same constraints, regardless of order. Note that this is \emph{not} the same as set-equal on the generated secrets. For example, the constraint sets
\[
\vC_1 = (1234:0A0B, 3456:0A0B)
\]
and
\[
\vC_2 = (1234:0A0B, 1256:0A0B)
\]
are not equal by definition, although they generate the same secrets.

Let $\vS$ denote the set of all codewords under a given set of rules. A few properties of constraint sets are shown below.

1. Not all subsets of $\vS$ can be generated from constraints. For example, in Bulls and cows, after the first guess, the number of remaining secrets will not be more than 1440; this means any proper subset with more than 1440 elements cannot be generated from constraints. 

Although there are as many as $2^5040$ subsets, only a fraction can be generated by constraints. If we consider equivalence, the number is even smaller and probably tractable.

2. If two constraint sets are equal, then the subsets generated from them are equal; if two subsets are different, and their generating constraints cannot be equal.

3. If two constraint sets are different, their generated secrets may or may not be equal. See the example above. 
%For a non-trivial example, consider the following simulated guessing process by different strategies:
%
%	 Secret: 7450
%	 # simple    minmax    entropy   maxparts
%	-------------------------------------------
%	 1 0123:0A1B 0123:0A1B 0123:0A1B 0123:0A1B
%	 2 1456:2A0B 1456:2A0B 1456:2A0B 1456:2A0B
%	 3 1478:1A1B 2435:1A1B 7418:2A0B 2475:1A2B
%	 4 1759:1A1B 0276:0A2B 0752:1A2B 0482:1A1B
%	 5 1896:0A0B 7450:4A0B 7450:4A0B 7450:4A0B
%	 6 2457:2A1B
%	 7 7450:4A0B
%Each column represents a filter that generates the single-element subset
%<code>{7450}</code>. [Note: however, they are reductible!]

\section{Color equivalence}

As a start-up, let's work with a simple but useful way to detect guess equivalence.

\subsection{Definitions}

\begin{definition}
(Color mask) A \emph{color mask}, denoted $\tau$, is a subset of the available colors. Since the number of colors in a game is small (6 for Mastermind and 10 for Bulls and cows), it is convenient to implement this subset as a bit-mask with present colors set to one. That's why we call it a mask here.
\end{definition}

Given a codeword $g$, define $\tau(g)$ to be the colors present in $g$. For example, $\tau(\cw{1442}) = \{1, 2, 4\}$. 

Given a codeword set $\mathcal{S}$, define $\tau(\mathcal{S})$ to be the colors present in any of the codewords in $\mathcal{S}$. That is, $\tau(\mathcal{S}) = \bigcup_{g \in \mathcal{S}} \tau(g)$. For example, $\tau(\{\cw{1442},\cw{2315} \}) = \{ 1, 2, 3, 4, 5\}$.

of a codeword is the set of colors present in the codeword. The color mask of a set of codewords is the set of colors present in any of the codewords.

A few of the important color masks are as follows.

$\tau_{\text{all}}$ is the set of all colors.

$\tau_{\text{free}}$ is the set of colors that have never been guessed. $\tau_{\text{used}}$ is the set of colors that have been guessed. We have $\tau_{\text{free}} \cup \tau_{\text{used}} = \tau_\text{all}$.

$\tau_{\text{excl}}$ is the set of colors that are excluded from the potential secrets.


\subsection{Algorithm}

\newcommand{\cmall}{\tau_\text{all}}
\newcommand{\cmfree}{\tau_\text{free}}
\newcommand{\cmexcl}{\tau_\text{excl}}

Denote by $\mathcal{F}_k$ a color equivalence filter. It is characterized by a pair of color masks: the free/fresh/unguessed/uncalled colors and the excluded colors. That is,
\[
\mathcal{F} = (\tau_\text{free}, \tau_\text{excl}) .
\]

Three operations are:

\emph{Initialize}. At the beginning of the game, there are no constraints. A color equivalence filter is initialized by
\[
\cmfree = \cmall, \cmexcl = \phi .
\]

\emph{Filter}. For each candidate $g \in \mathcal{G}$, check whether $g$ is the lexical minimum of its equivalence class. We check this by replacing all excluded colors with the same symbol (e.g. *), and replace the unguessed colors using suitable mapping.

\emph{Restrict}. Given a constraint $(g,r)$ and the set of remaining possibilities $\mathcal{S}$, we construct a new filter as $\mathcal{F}' = (\cmfree', \cmexcl')$, where
\[
\cmfree' = \cmfree \setminus \tau(g), \cmexcl' = \cmall \setminus \tau(\mathcal{S})  .
\]


\section{Constraint equivalence}

Here the definition of \emph{constraint equivalence} is rather restrictive. Ideally, constraint equivalence should be the same as partition equivalence, but this is not the case here.

Introduced by \cite{neuwirth81,koyama93}. 

[Constraint/filter equivalence]

It is easy to see that solving a game only depends on what colors have appeared before, and the relative peg position of the guesses. The particular colors or pegs guessed are not important. From this knowledge, we define the following.

\subsection{Definitions}

\begin{definition}
(Peg permutation) A \emph{peg permutation}, denoted $\pi_p$, permutes the pegs in a codeword. For example, the peg permutation
\[
\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 1 & 2 & 4
\end{pmatrix} 
\]
moves peg 1 to the 3rd place, peg 2 to the 1st place, peg 3 to the 2nd place, and peg 4 in its original place. The reordered sequence of the pegs is given by $\pi_p^{-1}$, which in this example is equal to
\[
\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 3 & 1 & 4
\end{pmatrix} .
\]
\end{definition}

\begin{definition}
(Color permutation) A \emph{color permutation}, denoted $\pi_c$, permutes the colors in a codeword. For example, the color permutation
\[
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
5 & 2 & 1 & 6 & 3 & 4
\end{pmatrix} ,
\]
replaces color 1 by color 5, color 2 as is, color 3 by color 1, etc.
\end{definition}

\begin{definition}
(Partial color permutation) A \emph{partial color permutation} permutes a subset of colors. The set of colors not involved in the partial color permutation are called \emph{free colors} and denoted by $\tau$.
% , and leave the rest colors unchanged
%with the additional attribute that only a subset of the mappings are subject to future changes. These mappings are called \emph{free} mappings. 
%, denoted $\Pi_c$, is an incomplete permutation of the colors where the mapping among some colors are fixed, but the mapping among the rest colors are not specified. 
For example, the partial color permutation
\[
\begin{pmatrix}
%1^* & 2^* & 3^* & 4^* & 5^* & 6^*  \\
%1^* & 2^* & 3^* & 4^* & 5^* & 6^* 
%1 & 2 & 3 & 4 & 5 & 6 \\
%\textbf{1} & 2 & 3 & 4 & 5 & 6 \\
%* & * & * & * & * & *
\underline{1} & \underline{2} & 3 & \underline{4} & 5 & \underline{6} \\
\underline{1} & \underline{2} & 5 & \underline{4} & 3 & \underline{6} 
\end{pmatrix} .
\]
permutes (and \emph{restricts}) colors \cw{3} and \cw{5}, and leaves the free colors (marked with an underline) unchanged.
\end{definition}

A class of (fully-restricted) color permutations can be generated from a partial color permutation $\pi_c$ and its associated set of free colors $\tau$ by composing the partial permutation with every possible permutation of the free colors. We denote such class of color permutations by $\Pi_c = \pi_c \circ S_\tau$.

%A partial permutation in this context is actually a \emph{permutation group} [see appendix] formed by composing the fixed mappings with all permutations of the free colors. We can conveniently denote it as $\Pi_c = \pi_c \circ \tau$, where $\pi_c$ is the color mapping already fixed, and $\tau$ is the set of unmapped colors.

\begin{definition}
(Codeword permutation) A \emph{codeword permutation}, denoted $\pi$, is the combination of a peg permutation $\pi_p$ and a (partial) color permutation $\pi_c$. We write it as $\pi = \pi_p \circ \pi_c$. Note that the actual order of applying the peg permutation or the color permutation first does not matter.
\end{definition}

Given codeword $g$, we denote the permuted codeword under $\pi$ as $\pi(g)$ or $g^\pi$. 
%Note that since a codeword usually does not contain all available colors, the mapping of unused colors does not matter when applying a color permutation to a given codeword.
To compute the image $h = (h_i)$ of a given codeword $g = (g_i)$ under a given permutation $\pi = \pi_p \circ \pi_c$, use the formula
\[
h_i = \pi_c\left(g_{\pi_p^{-1}(i)}\right) .
\]

%[Properties.] Some usual properties of permutations apply to codeword permutation as well.
%
%1) A codeword permutation is invertible, i.e.\ for any $\pi = (\pi_p, \pi_c)$, its inverse exists and is equal to $\pi^{-1} = (\pi_p^{-1}, \pi_c^{-1})$.

\begin{definition}
(Codeword equivalence) Two codewords $g$ and $h$ are \emph{equivalent} if and only if there exists a codeword permutation $\pi$ such that $g^\pi = h$.
\end{definition}

For example, \cw{1314} and \cw{5336} are equivalent because we can use the following (non-unique) permutation of pegs and colors to map \cw{1314} to \cw{5336}.
\[
\pi_p = 
\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 1 & 3 & 4
\end{pmatrix}
, \pi_c = 
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
3 & 2 & 5 & 6 & 1 & 4 
\end{pmatrix} .
\]

The equivalence relation defined above partitions a set of codewords into equivalence classes, where each equivalence class can be represented by an arbitrary element in that class, called a \emph{representative}. 
%All elements in the same equivalence class are equivalent to this representative.
%; i.e.\ for all $g$, there exists $\pi$ such that $g = g_0^\pi$.

\begin{definition}
(Constraint equivalence) [cite a few references] Let $\mathcal{C}_1$ and $\mathcal{C}_2$ be two ordered sets of constraints of the same size $k$. Let the guesses in $\mathcal{C}_1$ be $(g_1,g_2,\cdots,g_k)$ and the guesses in $\mathcal{C}_2$ be $(h_1,h_2,\cdots,h_k)$. Then constraint sets $\mathcal{C}_1$ and $\mathcal{C}_2$ are \emph{equivalent} if there exists a codeword permutation $\pi$ such that
$g_i^\pi = h_i$ for all $1 \le i \le k$.
\end{definition}

The intuition about equivalent constraints are rather simple: if we rearrange the peg positions and relabel the colors, then the two sets of constraints become exactly the same. Hence for the purpose of devising a strategy, we only need to work with one of them and the other follows automatically.

Note, however, that there is a strong restriction in the above definition: the responses in the constraints are ignored. This has two implications. On the one hand, constraints such as 
\[
\mathcal{C}_1 = \{ (1234:0A0B), (3456:2A0B) \}
\]
and
\[
\mathcal{C}_2 = \{ (1234:1A0B), (3456:0A2B) \}
\]
are considered equivalent, although they lead to drastically different potential secrets. On the other hand, constraints such as
\[
\mathcal{C}_1 = \{ (1234:0A0B), (1234:0A0B) \}
\]
and
\[
\mathcal{C}_2 = \{ (1234:0A0B), (4321:0A0B) \}
\]
are obviously not equivalent by definition, but from the first feedback \fb{0}{0} we could already exclude the colors \cw{1} -- \cw{4} from the potential secret, so any permutation of \cw{1234} should ideally be considered equivalent.

Despite the less-than-ideal properties of such definition, this equivalence relation is still commonly used \cite{neuwirth81,koyama93,francis10} because of its clarity, relative simplicity, and effectiveness for the first few guesses. A more powerful (but also more complex) equivalence definition will be introduced in the next section.

\subsection{Illustration}

To actually apply a constraint equivalence filter in practice, we implement an \emph{incremental filter}, as illustrated below.\footnote{The incremental filter described in this section is effectively the same technique used by \cite{francis10} to detect equivalence in the Bulls and cows game.}
An alternative, more generic method, which relies on \emph{graph automorphism}, will be introduced in the next section.

Given a set $\mathcal{C}$ of constraints and a set $\mathcal{G}$ of candidate codewords to filter for the next guess, we want to find all canonical codewords $g \in \mathcal{G}$ to be used as the next guess. There are a couple of ways to do this,\footnote{For example, one could \emph{generate} a list of canonical guesses from scratch, or \emph{filter} a supplied list of codewords for canonical guesses. Here we employ the second approach because of its simplicity, flexibility, and good performance in an implementation.}
and we employ a simple algorithm: traverse the set and keep the codewords that are lexically minimal in its equivalence class. That is, for each $g \in \mathcal{G}$, we find the lexically minimum codeword $g_0$ that is equivalent to $g$, and keep $g$ if and only if $g = g_0$. 
%We call $g_0$ the \emph{canonical representative} of $g$.

Note that in order for the algorithm to work correctly, the lexically minimal codeword of each equivalence class must be present in the candidate set $\mathcal{G}$.\footnote{
This requirement is satisfied in most practical application. The algorithm could be slightly modified to remove this requirement: instead of removing a non-canonical element, it could employ a subset union algorithm to label the equivalence class of each element. After all candidates are processed, it can scan the labels to find the canonical elements.
}


To find the lexically minimum codeword equivalent to $g$, we could permute $g$ in all possible ways and check if any of the permuted image is smaller than $g$. For a Mastermind game, there are 4 pegs and 6 colors. The total number of permutations is therefore $4! \times 6! = 24 \times 720 = 17280$. This number is much larger in the Bulls and Cows game with 4 pegs and 10 colors, which is equal to $4! \times 10! = 87,091,200$.

Therefore we need to iterate the permutations in a more efficient way. We first conveniently classify the codeword permutations by their peg permutation, i.e.\ those with the same peg permutation are put into the same class. Then, as it will turn out shortly, the permutations in each class can be written as
\[
\pi_p \circ \pi_c \circ S_\tau ,
\]
where $\pi_p$ is the peg permutation that represents the class, $\pi_c$ is a partial color permutation restricted by the supplied constraints under this peg permutation, and $S_\tau$ is the group of all permutations of the set of free colors.

%We first find the canonical representative given each possible peg permutation of $g$. We then take the minimum of these minimum as the global minimum. [TBC]

Let's illustrate the algorithm with 4 pegs and 6 colors. We first list all $4! = 24$ permutations of the pegs, $\pi_p^1$ to $\pi_p^{24}$, where $\pi_p^1$ is the identity permutation.

Next, for each peg permutation $\pi_p^i$, we associate with it a class of \emph{eligible} color permutations, $\Pi_c^i = \pi_c^i \circ S_\tau$, where $\pi_c^i$ is the partial color permutation restricted by the supplied constraints under this peg permutation, and $\tau$ is the set of free colors. 
%$\Pi_c$ hence denotes the set of all eligibal color permutations as the product of $\pi_c^i$ and all permutations of the colors in $\tau$. 

At the beginning of the game, there are no constraints; all colors are free, and every partial color permutation is unrestricted. We can conveniently write $\pi_c \circ S_\tau$ as
%We can conveniently write an identity permutation in the set of eligible color permutations as
\[
%\Pi_c^i = 
\begin{pmatrix}
%1^* & 2^* & 3^* & 4^* & 5^* & 6^*  \\
%1^* & 2^* & 3^* & 4^* & 5^* & 6^* 
%1 & 2 & 3 & 4 & 5 & 6 \\
%\textbf{1} & 2 & 3 & 4 & 5 & 6 \\
%* & * & * & * & * & *
\underline{1} & \underline{2} & \underline{3} & \underline{4} & \underline{5} & \underline{6} \\
\underline{1} & \underline{2} & \underline{3} & \underline{4} & \underline{5} & \underline{6} 
\end{pmatrix} ,
\]
where the underlined colors are controlled by $S_\tau$ and hence can be mapped freely.

To filter a set of codewords $\mathcal{G}$ to obtain canonical guesses, we check each codeword $g \in \mathcal{G}$ in order.\footnote{The particular order of traversal is not important, as long as the lexical minimum belongs to the set.} 
Take for example $g = \cw{1223}$. We iterate through each peg permutation $\pi_p^i$ to permute $g$. Apply for example the following peg permutation,
\[
\pi_p = 
\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 1 & 3 & 4
\end{pmatrix} ,
%\]
%whose associated partial color permutation is initially
%\[
%\Pi_c = 
%\begin{pmatrix}
%1^* & 2^* & 3^* & 4^* & 5^* & 6^*  \\
%1^* & 2^* & 3^* & 4^* & 5^* & 6^* 
%\end{pmatrix} .
\]
followed by the (eligible) identity color permutation.
The permuted codeword is $g' = \cw{2123}$. Since $g' \succ g$, we cannot yet conclude that $g$ is not lexically minimum in its equivalence class. We proceed as follows.

We are free to map the free colors in $g'$ to any free color. Given our objective is to find the lexical minimum, we start from the leftmost peg of $g'$, which contains the color \cw{2}. This is a free color, and it should be mapped to the smallest available free color, \cw{1}, to achieve lexical minimum. This also means we have to map the color \cw{1} to something else temporarily because we cannot have two colors map to the same value. For convenience we map it to \cw{2}. Thus we apply the following color permutation to $g' = \cw{2123}$,
\[
\pi_c = 
\begin{pmatrix}
\underline{1} & 2 & \underline{3} & \underline{4} & \underline{5} & \underline{6} \\
\underline{2} & 1 & \underline{3} & \underline{4} & \underline{5} & \underline{6} 
\end{pmatrix} ,
\]
which yields $\pi_c(g') = \cw{1213}$.

Note that \cw{1213} is already lexically smaller than \cw{1223}, so we can conclude that \cw{1223} is not the lexical minimum of its equivalence class and can thus remove it from the candidates. However, for illustration purpose here we show a few more steps.

Now proceed to the color on the second peg of $g'$, \cw{1}. Again, \cw{1} is not mapped in the color permutation, so we are free to choose its image. And for the same reason of achieving minimal lexicographical value, we map it to the smallest available free color, which in this case is \cw{2}. The resulting color permutation is
\[
\pi_c = 
\begin{pmatrix}
1 & 2 & \underline{3} & \underline{4} & \underline{5} & \underline{6} \\
2 & 1 & \underline{3} & \underline{4} & \underline{5} & \underline{6} 
\end{pmatrix} ,
\]
and the permuted codeword is $\pi_c(g') = \cw{1213}$. Repeat this until all pegs in $g'$ are processed, and we find the lexical minimum to be \cw{1213}, which is smaller than $g$. We then remove $g$ from the candidate set. 

Repeat the above steps for all peg permutations. If $g$ is lexically minimum in all these cases, then it is the lexical minimum of its equivalence class, and we can add it to the filtered set.

Above is an examine where all colors are free. Now suppose we have already have some constraints, so some colors are fixed. Without loss of generality, suppose that the constraint consists of just one guess $g_1 = \cw{3445}$. To find all canonical candidates for the second guess, we first need to \emph{restrict} the partial color permutations associated with each peg permutation. 

Take for example 
\[
\pi_p = 
\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 3 & 2 & 4
\end{pmatrix} , 
\Pi_c = 
\begin{pmatrix}
\underline{1} & \underline{2} & \underline{3} & \underline{4} & \underline{5} & \underline{6} \\
\underline{1} & \underline{2} & \underline{3} & \underline{4} & \underline{5} & \underline{6} 
\end{pmatrix} .
\] 
The permuted first guess is $\pi(g_1) = \cw{3445}$. In order for the permuted constraint to be equivalent, the permuted guess must be equal to $g_1$. This means we must map \cw{3445} to \cw{3445} in the color permutation. Thus we must restrict the associated color permutation as
\[
\Pi_c' = 
\begin{pmatrix}
\underline{1} & \underline{2} & 3 & 4 & 5 & \underline{6} \\
\underline{1} & \underline{2} & 3 & 4 & 5  & \underline{6} 
\end{pmatrix} .
\]

After restricting the partial permutation, we can apply the previous steps again. 
[The following example need to be changed to continue from the previous example] Suppose we come again to \cw{1123}. If we apply peg permutation $\pi_p^3$, the permuted representative becomes \cw{1213}. Now to find out what color permutations are eligible, note that the color 3 is already fixed in the partial permutation; only colors 1 and 2 are free to be mapped. We could therefore map them freely among the unrestricted colors, i.e.\ $\{1, 2, 6\}$, and mark all resulting codewords as equivalent to \cw{1123}.

Note that given a set of constraints, not all peg permutations can yield an eligible color permutation. For example, consider the peg permutation
\[
\pi_p = 
\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 2 & 4 & 3
\end{pmatrix} .
\]
When applied to $g_1 = \cw{3445}$, we get $\pi_p(g_1) = \cw{3454}$. However, there is no way whatsoever to map \cw{3445} to \cw{3454}, because \cw{4} would have to be mapped to both \cw{4} and \cw{5}, which is impossible. In this case, we conclude that this peg permutation is \emph{ineligible} and remove it from further consideration.

\subsection{Algorithm}

%Given a set of $k$ constraints, 
%%$\mathcal{C}_k = \{ (g_i,r_i) \given 1 \le i \le k \}$, 
%$\mathcal{C}_k = \{ (g_1,r_1), \cdots, (g_k, r_k) \}$, 
%a \emph{constraint equivalence filter}, denoted $\mathcal{F}_k$, produces a short-list of canonical codewords for the next guess.

A constraint equivalence filter is characterized by the set of eligible codeword permutations which map existing constraints to themselves. These permutations 
can be classified into $m$ classes according to their peg permutation. The permutations in the $i$th class can be written as the product of the peg permutation $\pi_p^i$, the associated partial color permutation $\pi_c^i$, and the symmetric group of the free colors $S_\tau$ (which is the same across all $i$). 

Thus, we can write a constraint equivalence filter as
\[
\mathcal{F}_k = \bigcup_{i=1}^m \pi_p^i \circ \pi_c^i \circ S_\tau ,
\]
where $m$ is the number of eligible peg permutations.

Three operations are defined for a constraint equivalence filter:

\emph{Initialize}. At the beginning of the game, there are no constraints. Hence the initial filter, $\mathcal{F}_0$, is set to 
\[
m = \text{number of pegs}!, \pi_c^i = (), \tau = \{1, 2, \ldots, c \}.
\]

\emph{Filter}. To filter a set $\mathcal{G}$ of candidate codewords for canonical guesses, we check each codeword $g \in \mathcal{G}$ in order.\footnote{The particular order of traversal is not important, as long as the lexical minimum belongs to the set.} 
Given $g$, we check each eligible peg permutation in $\mathcal{F}$. For peg permutation $i$, we first permute $g$ to get $g' = \pi_p \circ \pi_c (g)$. If $g' \prec g$, then $g$ is not minimum. Otherwise, let $g' = (c_1, c_2, c_3, c_4)$. For each $j = 1$ to $4$, if $j \in \tau$, then map $j$ to the smallest color in $\tau$, etc.


%Formally, let $\mathcal{F} = \left\{(\pi_p^i, \pi_c^i \circ \tau) \given 1 \le i \le m \right\}$ be an incremental equivalence filter containing $m$ (partial) codeword permutations. Every partial color permutation has the property that some of the colors are restricted, while the rest are not. Let the set of free colors be $\tau_i$. As will show shortly, $\tau_i$ is the same across all permutations in a filter, so we can denote them by $\tau$. Also, for each $\Pi_c^i$, we pick a representitive $\pi_c^i \in \Pi_c^i$. Hence the filter can be written as
%\[
%\mathcal{F} = \left\{(\pi_p^i, \pi_c^i; \tau) \given 1 \le i \le m \right\} .
%\]

\emph{Restrict}. Given a filter $\mathcal{F}_k$ that satisfies all existing constraints $\mathcal{C}_k$. When a constraint $(g, r)$ is added, we construct a new filter $\mathcal{F}_{k+1} \subseteq \mathcal{F}_k$ by selecting the permutations in $\mathcal{F}_k$ that maps $g$ to itself. This is effectively restricting the partial color permutation associated with each peg permutation.
%so that
%$\pi_c^i ( \pi_p^i (g) ) = \pi_p^i (g)$ for all $\pi_c^i \in \Pi_c^i$. 
%$\pi(g_k) = g_k$ for all $\pi \in \mathcal{F}_{k+1}$.

[TBC] It can be seen from the above requirement that any color that is mapped from in a partial color partition is also mapped to, and any color that is not mapped in one direction is also not mapped in the other direction. In fact, the unmapped colors are those \emph{unused} in any of the prior constraints. This means this equivalence filter fully considers the ``unguessed color equivalence'' described in the previous section.


As we proceed in the game, we are supplied with more constraints. The partial color permutation associated with each peg permutation gets more restrictive with each
added constraint, and more peg permutations becomes ineligible and gets removed. Finally we will be left with only the identity codeword permutation, where every codeword will become a representative of its own equivalence class.
%Hence we call it "incremental equivalence detection".

\subsection{Results}

Applying the constraint equivalence filter described in this section, we find 5 canonical guesses for the first round of a standard Mastermind game (p4c6r), listed in Table \ref{tab:canonical-mastermind}. Listed alongside is the number of canonical guesses in the second round given each initial guess.
\begin{table}[h]
\begin{center}
\begin{tabular}{c c}
\hline
\hline
$g_1$ & $\#\{g_2\}$ \\
\hline
\cw{0000} & 12 \\
\cw{0001} & 53 \\
\cw{0011} & 39 \\
\cw{0012} & 130 \\
\cw{0123} & 57 \\
\hline
\hline
\end{tabular}
\caption{Canonical 1st and 2nd guesses in Mastermind}
\label{tab:canonical-mastermind}
\end{center}
\end{table}

Applying the same filter to the Bulls and cows game (p4c10n) yields only one canonical initial guess, \cw{0123}, and 20 canonical guesses for the second round. They are listed in Table \ref{tab:canonical-bulls} along with the number of canonical guesses for the third round.\footnote{The table on page 7 of \cite{francis10} contains the same information; however their number for \cw{0456} is 373 and their number for \cw{4567} is 218.}
\begin{table}[h]
\begin{center}
\begin{tabular}{c c | c c | c c | c c}
\hline
\hline
$g_2$ & $\#\{g_3\}$ & $g_2$ & $\#\{g_3\}$ & $g_2$ & $\#\{g_3\}$ & $g_2$ & $\#\{g_3\}$ \\
\hline
\cw{0123} & 20  & \cw{0214} & 270  & \cw{1032} & 39  & \cw{1234} & 501  \\
\cw{0124} & 107 & \cw{0231} & 75   & \cw{1034} & 270 & \cw{1245} & 1045 \\
\cw{0132} & 67  & \cw{0234} & 501  & \cw{1045} & 295 & \cw{1435} & 541  \\
\cw{0134} & 270 & \cw{0245} & 1045 & \cw{1204} & 175 & \cw{1456} & 1012 \\
\cw{0145} & 295 & \cw{0456} & 363  & \cw{1230} & 59  & \cw{4567} & 180  \\
\hline
\hline
\end{tabular}
\caption{Canonical 2nd and 3rd guesses in Bulls and cows}
\label{tab:canonical-bulls}
\end{center}
\end{table}

[consistent with all prior guesses]

\section{Partition equivalence}

State/Partition Equivalence

This is the finest-grained definition of equivalence, but is complex in implementation.

\begin{definition}
(Partition) Let $(b_1, b_2, \cdots, b_r)$ be the ordered set of distinct feedbacks in a game. Then the \emph{partition} of a codeword set $\mathcal{S}$ by a codeword $g$ is a partition of $\mathcal{S}$ into ordered cells $(V_1, V_2, \cdots, V_r)$ such that the codewords in $V_i$ compare to $g$ yields $b_i$.
\end{definition}

\begin{definition}
(Partition equivalence.) Given two partitions $P_1 = (V_1, V_2, \cdots, V_r)$ and $P_2 = (V'_1, V'_2, \cdots, V'_r)$ of a codeword set $\mathcal{S}$. $P_1$ and $P_2$ are \emph{equivalent} if there exists codeword permutation $\pi$ such that $V_i^\pi = V'_i$ for all $1 \le i \le r$. That is, $\pi$ maps the cells in $P_1$ to the same cells in $P_2$. [color preserving permutation]
\end{definition}

\begin{definition}
(Guess equivalence.) Given a set of potential secrets $\mathcal{S}$, two guesses $g_1$ and $g_2$ are \emph{equivalent} if the partitions given by $g_1$ and $g_2$ on $\mathcal{S}$ are equivalent.
\end{definition}

[Can we show that partition equivalence is the \emph{finest} equivalence relation that preserves the \emph{structure} of a strategy tree?] Of course we need to define the motivation and what is a ``structure'' first.

\section{Spacial Equivalence}

The codewords can be thought of as points in a space. The comparison feedback between two codewords can be thought as the distance between the points. For a formal treatment on distance, see \cite{stuckman06}.

Can we define guess equivalence based on the guess's relative position to all the remaining secrets or the whole secret space?

For example, for Bulls and cows, at the beginning of the game all guesses are equivalent as the first guess. This is because the entire codeword set is completely symmetric.

However, for the Mastermind game, there are a few distinct initial guesses. It looks like right that these guesses have different relative spacial position relative to the codeword space.

Consider again when there is one secret left. Obviously [?] two guesses are equivalent if they yield the same feedback against this potential secret (if no repetition of digit is allowed). How about for Mastermind which allows repetition?

Also need to consider when two secrets are left, etc.

[And is such equivalence correct? Is it equivalent to partition equivalence? Is it weaker than partition equivalence? How to implement?]

\section{Chaining Multiple Filters}

[Note that constraint equivalence is strictly weaker(stronger?) than partition equivalence. For example, consider the first constraint 1234:0A0B. Then for the next guess, 1156 or 1256 are obviously the same (they both contain excluded colors 1, 2). However, 1156 and 1256 are clearly not equivalent under constraint equivalence. This is because constraint equivalence doesn't use the info of the feedback.

One way to deal with this is to use both. If two guesses are equivalent under any measure, then they are equivalent. This approach is discussed in this section.

Alternatively, we could combine the two. When there are a lot of possibilities, we compute constraint equivalence. When there are a few possibilities, we compute partition equivalence. This approach is discussed in ?? future sections.]
 
The equivalence filters described above vary in complexity and performance. More complex filters tend to produce fewer canonical guesses, but at the cost of higher computational overhead. If the computational overhead is too high, the benefit of filtering could be offset.

It is therefore useful in practice to chain multiple equivalence filters together by feeding the output of one filter as input into the next filter. This has two benefits: i) it potentially reduces the number of canonical guesses by testing different equivalence relations, and ii) it speeds up the computation of the latter filter by supplying potentially fewer candidates as input.\footnote{This relies on the assumption that the computational complexity of a filter grows with the number of candidates, which is satisfied for the filters described in the previous sections.}
Below we discuss some issues in implementing such a filter chain.

\begin{definition}
(Composite equivalence) Let $R_1$ and $R_2$ be two equivalence relations defined on the codeword set $\vS_0$. Then $R$ is a \emph{composite equivalence relation} of $R_1$ and $R_2$ if for any $g_1, g_2 \in \vS_0$, $g_1 R g_2$ if and only if $g_1 R_1 g_2$ or $g_1 R_2 g_2$. We denote it as $R = R_1 \vee R_2$. The $\vee$ operator is commonly known as the \emph{join} of the partitions induced by the two equivalence relations.\footnote{See \url{http://en.wikipedia.org/wiki/Lattice\_(order)}.}
\end{definition}

\begin{definition}
(Equivalence refinement) For two equivalence relations $R_1$ and $R_2$, $R_1$ is called \emph{finer} than $R_2$ (and $R_2$ \emph{coarser} than $R_1$) if any pair of elements that are equivalent under $R_1$ are also equivalent under $R_2$. It is easy to see that if $R_1$ is finer than $R_2$, then $R_1 \vee R_2 = R_2$.
\end{definition}

\begin{definition}
(Compatible relations) Let $R_1$ and $R_2$ be two equivalence relations defined on the set $S$. Then $R_1$ and $R_2$ are called \emph{compatible} if for any $g \in \vS$, $[g]_{R_1} \subseteq [g]_{R_2}$ or $[g]_{R_2} \subseteq [g]_{R_1}$. Intuitively, this means $R_1$ is a refinement or $R_2$ for part of the set, and $R_2$ is a refinement of $R_1$ for the rest part of the set. In particular, any equivalence relation is compatible with its refinement.
\end{definition}

\begin{definition}
(Discrete equivalence) A \emph{discrete} equivalence relation is an equivalence relation where every element is equivalent only to itself. A discrete equivalence relation is finer than any other equivalence relation defined on the same set.
\end{definition}

\begin{definition}
(Unit equivalence) A \emph{unit} equivalence relation is an equivalence relation where all elements are equivalent. A unit equivalence relation is coarser than any other equivalence relation defined on the same set.
\end{definition}

\begin{definition}
(Trivial equivalence) Discrete and unit equivalence relations are collectively called \emph{trivial} equivalence relations.
\end{definition}

\begin{definition}
(Simple filter) Let $R$ be an equivalence relation defined on a set $S$. A \emph{simple filter} of $\vS$ with respect to $R$ is a function that takes as input a subset $\vG \subseteq \vS$ and produces as output a set containing a representative for each class of equivalent elements in $\vG$.\footnote{Such output is known as the set of \emph{class representatives} of $\vG$; see \url{http://mathworld.wolfram.com/ClassRepresentative.html}. }
\end{definition}

One way to implement a composite equivalence filter is using \emph{disjoint sets}.\footnote{See \url{http://en.wikipedia.org/wiki/Disjoint-set\_data\_structure}.} However, this approach does not reduce the computational complexity of the second filter, and is not useful when one equivalence is finer than the other. In addition, the data structure is more complex to implement.

Therefore, we prefer to implement a composite filter by \emph{chaining} the individual filters. That is, given candidate set $\vG$, we first apply the first filter to get $\vG_1 = \vF_{R_1}(\vG)$, and then apply the second filter to get $\vG_2 = \vF_{R_2}(\vG_1)$. If we can ensure $\vG_2 = \vF_{R_1 \vee R_2}(\vG)$, then this method is a simple and efficient way to compute the composite.

However, arbitrary equivalence filters for arbitrary equivalence relations \emph{cannot} be chained in the above manner to produce the correct result. Let's look at a counter-example. Take a set of three elements, $X = \{1, 2, 3\}$, and take the following equivalence relations:
\begin{align}
R_1 &= \{ \{1, 2\}, \{3\}  \} , \notag \\
R_2 &= \{ \{1\}, \{2,3\}  \} . \notag 
\end{align}
It follows that the composite equivalence relation is $R_1 \vee R_2 = \{ \{ 1, 2, 3 \} \}$.

Now suppose we use a ``natural'' filter $\vF$ that keeps elements in the input sequence that are not equivalent to any of the prior elements. Then we have $\vF_{R_1}(X) = \{ 1, 3 \}$. If we in turn feed this output to the next filter, we get $\vF_{R_2}(\{1,3\}) = \{1,3 \}$. However, this result is not desired because $\vF_{R_1 \vee R_2}(X) = \{1\}$.

This counter-example can be generalized to show that for arbitrary choices of equivalence relations and simple filters, we are not guaranteed to get the desired result by simply chaining individual filters. This is formalized by the following theorem.

\begin{theorem}
Let $R_1$ be a non-trivial equivalence relation defined on a set $\vS$, and let $\vF_{R_1}$ be a simple filter. Then there exists equivalence relation $R_2$ and set $\vG \subseteq \vS$ such that for any simple filter $\vF_{R_1 \vee R_2}$ and $\vF_{R_2}$, $\vF_{R_1 \vee R_2}(\vG) \ne \vF_{R_2}(\vF_{R_1}(\vG))$.
\end{theorem}

\begin{proof}
Since $R_1$ is non-trivial, there must exist a set of three distinct elements $\vG = \{ g_1, g_2, g_3 \} \subseteq \vS$ such that $R_1$ partitions $\vG$ as
\[
\vG / R_1 = \{ \{ g_1, g_2 \}, \{ g_3 \} \} .
\]
It follows that $\vF_{R_1} (\vG) = \{ g, g_3 \}$ where $g$ is one of $g_1$ and $g_2$. 
Now define equivalence relation $R_2$ on $\vS$ as
\[
\vS / R_2 = \{ \{g\}, \vS \setminus \{g\} \} .
\]
It is easy to see that $R_1 \vee R_2$ is the unit equivalence $\{ \vS \}$, so $\vF_{R_1 \vee R_2}(\vG)$ contains only one element. However, $\vF_{R_2}(\vF_{R_1}(\vG)) = \vF_{R_2}(\{ g, g_3 \}) = \{ g, g_3 \}$.
\end{proof}

The above theorem implies that for a non-trivial equivalence relation $R_1$, it is impossible to implement a ``universal'' simple filter that can be chained to an arbitrary equivalence relation $R_2$. However, for specific choices of $R_2$, in particular those compatible with $R_1$, this actually is possible. This is shown by the following theorem.

\begin{theorem}
Let $R_1$ and $R_2$ be two compatible equivalence relations defined on a set $\vS$, and let $\vF_{R_1}$, $\vF_{R_2}$, and $\vF_{R_1 \vee R_2}$ be simple filters. Then $\vF_{R_1 \vee R_2}(\vG) = \vF_{R_2}(\vF_{R_1}(\vG))$ for all $\vG \subseteq \vS$.
\end{theorem}

This is quite obvious, so we are not going to elaborate the proof here.

\begin{theorem}
Let $R_1$ and $R_2$ be two non-compatible equivalence relations defined on a set $\vS$, and let $\vF_R$ denote a simple filter for $R$. Then for any $\vF_{R_2}$, there exists $\vF_{R_1}$ and $\vG \subseteq \vS$ such that $\vF_{R_2}(\vF_{R_1}(\vG)) \ne \vG / (R_1 \vee R_2)$.
\end{theorem}

\begin{proof}
Since $R_1$ and $R_2$ are not compatible, there must exist a set of three distinct elements $\vG = \{ g_1, g_2, g_3 \} \subseteq \vS$ such that $R_1$ and $R_2$ partitions $\vG$ as
\[
\begin{array}{ r l }
R_1: & \{ g_1, g_2 \}, \{ g_3 \} , \\
R_2: & \{ g_1 \}, \{ g_2, g_3 \} .
\end{array}
\]
It is easy to see that $g_1, g_2, g_3$ are all equivalent under $R_1 \vee R_2$, so $\vG / (R_1 \vee R_2)$ contains only one element.
Now define $\vF_{R_1} (\vG) = \{ g_1, g_3 \}$. It then follows that
\[
\vF_{R_2}(\vF_{R_1}(\vG)) = \vF_{R_2}(\{ g_1, g_3 \}) = \{ g_1, g_3 \} \ne \vG / (R_1 \vee R_2) .
\]
\end{proof}

%The above theorem shows that natural filters cannot be chained for arbitrary equivalence relations and arbitrary input. However, for specific pairs of equivalence relations, they may still be chained. In particular, if one equivalence is finer than the other, then it is easy to see that they can be chained.\footnote{This is why we require $R_1$ to be non-trivial in the above theorem, since a discrete relation is finer than any relation, and any relation is finer than a unit relation.}

The counter-example and the theorem above means in order to chain filters on arbitrary relations, we must impose additional restriction on how a filter returns representative elements. For practical usefulness, we define a class of \emph{canonical} filters which satisfy this.

\begin{definition}
(Canonical filter) A \emph{canonical filter} is an equivalence filter that only returns representatives that are minimum in their respective equivalence classes. Formally, let $\prec$ be a total order on the set $\vS_0$ of all codewords.\footnote{A convenient example of such total order is the lexicographical order.}
Let $R$ be an equivalence relation that partitions $\vS_0$ into $r$ cells, where the minimum element (with respect to $\prec$) of the $i$th cell is denoted by $m_i$. Then a \emph{canonical filter}, $\vF$ is a function $\vS_0 \rightarrow \vS_0$ defined by
\begin{equation}
\vF(\vG) = \vG \cap \left\{ m_i \given 1 \le i \le r \right\} \text{ for any } \vG \subseteq \vS_0 . \label{eq:canonical-filter-1}
\end{equation}
In particular, if some $m_i$ is not in $\vG$, then its equivalence class is excluded from the output.
\end{definition}

Next we show that we can safely chain canonical filters together to produce the desired output efficiently.

\begin{theorem}
Let $\mathcal{F}_1$ and $\mathcal{F}_2$ be the canonical filters for equivalence relations $R_1$ and $R_2$. Let $\vF$ be the canonical filter for equivalence relation $R = R_1 \vee R_2$. Then $\vF(\vG) = \vF_2(\vF_1(\vG))$ for any $\vG \subseteq \vS_0$.
\end{theorem}

\begin{proof}
Before going into details, we illustrate the idea with an example of 7 codewords. A $\times$ sign indicates a representative of one of the canonical filters, and a $\otimes$ sign indicates a representative of both filters.
\[
\begin{array}{r c c c c c c c }
      & g_1 & g_2 & g_3 & g_4 & g_5 & g_6 & g_7 \\
\vF_1: & \otimes &        & \times & \otimes & & \times & \\
\vF_2: & \otimes & \times &        & \otimes & &        & \times
\end{array}
\]

Formally, let $\vu = (u_1, \cdots, u_r)$ and $\vv = (v_1, \cdots, v_s)$ be the ordered set of minimum representatives of $\vS_0 / R_1$ and $\vS_0 / R_2$ respectively. According to equation \eqref{eq:canonical-filter-1}, we have
\[
\vF_1(\vG) = \vG \cap \vu, \vF_2(\vG) = \vG \cap \vv.
\]
Let $\vw = \vu \cap \vv = (w_1, \cdots, w_t)$. We now show that $\vw$ is the set of minimum representatives of $\vS_0 / (R_1 \vee R_2)$.

First, it is obvious that any $w_{k_1}, w_{k_2} \in \vw$ are not equivalent under $R_1$ or $R_2$. Otherwise, suppose $w_{k_1} \sim w_{k_2}$ under $R_1$, then the corresponding elements $u_{i_1}, u_{i_2} \in \vu$ are equivalent under $R_1$, which is contradictory to the definition of $\vu$.

Next, we show that any given $w \in \vS_0$ is equivalent to some $w_k \le w$ under $R = R_1 \vee R_2$. Given $w$, there exists $u_i \le w$ and $v_j \le w$ which are equivalent to $w$ under $R_1$ and $R_2$ respectively. By definition of $R$, $w$ is equivalent to $u_i$ and $v_j$ under $R$ as well. If $u_i = v_j$, then $w \in \vw$ and the statement is true. Otherwise, suppose without loss of generality that $u_i < v_j$. Since $w \sim u_i$ under $R$, we just need to show that $u_i$ is equivalent to some $w_k \le u_i$. Repeat this process until some $u_i = v_j$, or we come to $u_1 = v_1 = \min \vS_0$, where the statement trivially holds.

The above two paragraphs show that $\vw$ is the minimum representative of $R$. [Still need to show the $R$ defined this way satisfies $R = R_1 \vee R_2$?] It then follows that for any $\vG \subseteq \vS_0$,
\[
\vF(\vG) = \vG \cap \vw = \vG \cap (\vu \cap \vv ) = (\vG \cap \vu) \cap \vv
= \vF_2(\vF_1(\vG)) .
\]

\end{proof}

%However, if each filter in implemented in a way such that it keeps a specific element as the representative, such as the lexical minimum of its equivalence class of each particular equivalence, then chaining them together may incorrectly drop out canonical guesses. This section discuss the conditions under which chaining them together will still produce correct results.

